Using a multi-word “passphrase” instead of a password has been suggested for decades as a way to thwart guessing attacks. The idea is now making a comeback, for example with the Fastwords proposal which identifies that mobile phones are optimised for entering dictionary words and not random character strings. Google’s recent password advice suggests condensing a sentence to form a password, while Komanduri et al.’s recent lab study suggests simply requiring longer passwords may be the best security policy. Even xkcd espouses multi-word passwords (albeit with randomly-chosen words). I’ve been advocating through my research though that authentication schemes can only be evaluated by studying large user-chosens distribution in the wild and not the theoretical space of choices. There’s no public data on how people choose passphrases, though Kuo et al.’s 2006 study for mnemonic-phrase passwords found many weak choices. In my recent paper (written with Ekaterina Shutova) presented at USEC last Friday (a workshop co-located with Financial Crypto), we study the problem using data crawled from the now-defunct Amazon PayPhrase system, introduced last year for US users only. Our goal wasn’t to evaluate the security of the scheme as deployed by Amazon, but learn more how people choose passphrases in general. While this is a relatively limited data source, our results suggest some caution on this approach.
Amazon’s system requires a multi-word (minimum 2) passphrase which is globally unique. This provided an oracle for our experiment: in the original version of the site, error messages would clearly indicate if a phrase was already chosen (as opposed to being blacklisted or invalid), letting us test large lists of phrases to see what was taken. Our first experiment was a dictionary attack using lists of movie titles, sports team names, and dozens of other types of proper nouns crawled from Wikipedia, along with idiomatic phrases crawled from soruces like Urban Dictionary. We found about 8,000 phrases using a 20,000 phrase dictionary. Using a very rough estimate for the total number of phrases and some probability calculations, this produced an estimate that passphrase distribution provides only about 20 bits of security against an attacker trying to compromise 1% of available accounts. This is far better than passwords, which are usually under 10 bits by this same metric, but not high enough to make online guessing impractical without proper rate-limiting. Curiously, it’s close to estimates made using Kuo et al.’s published numbers on mnemonic phrases. It also shows that significant numbers of people will blatantly ignore security advice about choosing nonsense phrases and choose things like “Manchester United” or “Harry Potter.”
After this experiment, we did a few experiments to test the linguistic properties of phrases by generating potential phrases according to their distribution in large linguistic corpora (we used the British National Corpus and Google n-gram corpus). Some clear trends emerged—people strongly prefer phrases which are either a single modified noun (“operation room”) or a single modified verb (“send immediately”). These phrases are perhaps easier to remember than phrases which include a verb and a noun and are therefore closer to a complete sentence. Within these categories, users don’t stray too far from choosing two-word phrases the way they’re actually produced in natural language. That is, phrases like “young man” which come up often in speech are proportionately more likely to be chosen than rare phrases like “young table.”
This led us to ask, if in the worst case users chose multi-word passphrases with a distribution identical to English speech, how secure would this be? Using the large Google n-gram corpus we can answer this question for phrases of up to 5 words. The results are discouraging: by our metrics, even 5-word phrases would be highly insecure against offline attacks, with fewer than 30 bits of work compromising over half of users. The returns appear to rapidly diminish as more words are required. This has potentially serious implications for applications like PGP private keys, which are often encrypted using a passphrase. Users are clearly more random in “passphrase English” than in actual English, but unless it’s dramatically more random the underlying natural language simply isn’t random enough. Exploring this gap is an interesting avenue for future collaboration between computer security researchers and linguists. For now we can only be comfortable that randomly-generated passphrases (using tools like Diceware) will resist offline brute force.
My most commonly used passphrase is the romanised form of a foreign language sentence. Makes dictionary attacks interesting as the words used are typically not in English dictionaries 🙂
What about swapping the first letters of randomly-chosen words? Or another siple rule. Is it safer?
Pytamy: there are 5 choose 2 = 10 ways to swap the first letters of two randomly chosen words out of five. That might net you three bits, but it won’t do too much.
I right now choose these sorts of passwords using a random passphrase generator which just reads in my dictionary and chooses several random words. Some example output is:
drostie@signy:~$ words 4
(Line entropy: 64.7055497954 bits.)
Swazi orthodoxy Indus prospectives
drostie@signy:~$ words 4
(Line entropy: 64.7055497954 bits.)
asps graying outweighing baddest
Whether you can remember “asps graying outweighing baddest” is a different story, but if you’re a touch typist then it’s a pretty quick password to type.
For one sensitive application, I use a 4-word passphrase using words from two different languages and appending a few numeric digits to the shortest word.
My rough estimate is that this gives me about 15 extra bits with very little extra difficulty to remember.
Could you add a twitter feed (e.g. YOURLS) for your blog? People would love it!
After reading Moonwalking With Einstein I’ve moved to three word passphrases that follow the Subject->Action->Object format. They need not be sensible though. Things like
Obama Punting Cornflakes
or
Grammy Curling Pumpkins
Both of those are over 80 bits, and you’ll never forget them. In fact, if you read this, you’ll never get the image of Obama punting a box of cornflakes out of your head.
Very interesting.
Also why I made a little dictionary-embedded-in-a-bash script:
http://blog.0x10.co.uk/2012/01/passphrase-generator.html
e.g.
$ ./ppgen.sh
Does Brazil quotas message
amount losers sing Oregon
or
$ ./ppgen.sh 1 5
Commodity dioxide Boris unit drop
When recommending the use of a passphrase vs a password, I also recommend inserting a random symbol/number (or more) mid-word, making letter/number/symbol replacements (other than the usual suspects), and/or introducing intentional misspellings. “eyeHA!TEpa88wordz” is pretty simple to remember and shouldn’t have the issues mentioned above.
Have you considered releasing the dictionaries/wordlists you compiled? I think they could be useful to the InfoSec community as a whole.
@Jonathan – Given that a vocabulary of around 16000 words covers 97.8% of the written texts, would it not be true that brute force against your ‘subject – action – object’ triple is fairly trivial?
The entropy quoted in the comments are highly, highly optimistic:
Jonathan writes:
“””Obama Punting Cornflakes
or
Grammy Curling Pumpkins
Both of those are over 80 bits
“””
This assumes that you have more than 100 million subjects (2 ^ (80/3)), actions, and objects that you randomly choose from. Alternatively, you need more in one category to have less in another one. So the minimum dictionary size is 300 million words.
I would like to see the dictionary you’re using!
Jimmy writes:
“”For one sensitive application, I use a 4-word passphrase using words from two different languages and appending a few numeric digits to the shortest word.
My rough estimate is that this gives me about 15 extra bits
“””
Assuming using two languages doubles the dictionary size, your 4 word passphrase cannot gain more than 3 bits of entropy from this (remember, I already know that you use both languages). Then “a few”, say 3 numeric digits could add 10 bits of entropy, but only if you chose it randomly.
By not doing this randomly, you can expect to give away roughly 50% of your entropy advantage (taken out of thin air, like your estimate).
I would give Jimmy at most 6.5 bits of entropy.
Ha, excellent point, the one thing that I remember from studying cryptography was the clever way mathematicians (or hackers) figure out to reduce the randomness. Here is a great example: password cracker can eliminate many words, guessing the order is “subject – action – object”.
Passphrases are good, but even better if you apply some additional rules to break the pattern. How about starting the sentence with a , or use doublespase within the sentence? How about starting or ending the sentence with another special character? Breaking the expected pattern means more complex passphrases. Eg: ” What a lame password!” or “What a lame password! ” (note the doublespace between the words and the space after !).
Remember: space is also a special character, and by adding just one unexpected character within the phrase the passphrase will be way more difficult to break.
I take a couple of lines from a favorite song and acronymize (?) them. Depending on the system, I might use a comma between the lines (though some systems don’t take special characters – punctuation, spaces, etc. – in passwords), and depending on the song I might use a numeral instead of the first letter of the word. So, for instance, “Oh, say can you see by the dawn’s early light” would generate “O,scysbtdel” as a password. In fact, I would break it up even more: “O,scys,Btdel” would be more likely – a comma for the line break and capitalizing the second line. (Also, I tend to use longer song lyrics.) The benefit of this is that I know the songs, I know the lyrics well, and if I *have* to leave myself a hint, I can do it pretty subtly (so I might leave a hint of “Anthem” or, even more obliquely, “Play ball!” for the above example).
I’m not a security person, so I now expect the experts to tell me why this is a lousy idea. 🙂
I use 4 or 5 nouns for pass phrases. Its not a phrase, but I can remember it easily by visualizing the actual nouns in my mind. I’m curious what the entropy is of this technique.
As soon as you reduce the search scope, e.g. “I use four or five nouns” then you reduce the search pace considerably, since the attacker can now remove all non-nouns from my search space. I have to know that you use four nouns to be able to do this (and you have just shared this with the world).
One take away I have from this is humans are very bad at guessing how much entropy their passwords have: We constantly over-assess how secure our passwords are and overestimate the effects of constraints on passwords at adding security.
I’m going to assert that security researchers may be better at this that others, but I suspect that even their guesses (6.5) above may be over-estimating the reality.
Shameless plug – I threw together a quick and dirty AJAX-ey website to generate memorisable passphrases following the XKCD system – check it out: Memorable PassPhrase
2 words – password haystacks
https://www.grc.com/haystack.htm
An interesting spin is to look how the dictionary is generated. Each dictionary are generated within a language. So one could use two or more languages. If You for example read Spanish in high school, You could for example make the word corazonstart (heartstart). Th more languages, the better. And don’t forget about math and science. Some mnemonics is not regarded as words, but often You know them by heart. The electrical formula involving voltage resistance current is shorten U=R*I so You can add corazonURIstart, and thus You only have to remember heartattack. And the words “heartattack” and “brokenheart” are words that You can use on a post-it as the result of a heart attack is the need for some current to make the heart start.
Personally I also include swearwords in my multi-word passwords. It might not make them harder to crack, but it does make you feel better on a bad day when you type them in 🙂
Debate on multiword passphrases is a moot point for a huge number of websites. I can’t begin to list the number of sites that prevent me from using spaces (or even special characters!) in passwords. Twitter – I’m looking at you.(but not only you)
Seems to me this is a far more important issue than whether passphrases offer more protection. It’s inexcusable for some of the most used (and incidentally most password compromised) sites to prevent a user from setting up at least a moderately more secure login.
How inconsistent is this with the old heuristic that English text contains about 1.2 bits of entropy per non-space character?
So to protect a 128-bit symmetric key and not have the passphrase be the weak point, you’d need at least 107 non-space characters in your passphrase, and for the phrase to not exist anywhere in published literature
Those 20 bits you get are really many more if the system protected does _not_ require the password to be a passphrase. If the system allows for arbitrary passwords, then a passphrase is only one of the many possible ways to generate a password.
>Donald wrote: “””Assuming using two languages doubles the dictionary size, your 4 word passphrase cannot gain more than 3 bits of entropy from this (remember, I already know that you use both languages).”””
But you do not know which foreign language is used unless he tells you. So you need an even larger dictionary, more than double.
“Debate on multiword passphrases is a moot point for a huge number of websites. I can’t begin to list the number of sites that prevent me from using spaces (or even special characters!) in passwords. ”
It’s moot because websites don’t let someone try a million passwords in a few seconds. A short dictionary password that has no special association with the user is plenty of security there.
Given that most of the proposals for ways to generate enough entropy yield things too hard to remember or type for an ordinary person to accept, it looks like we simply can’t use remembered or typed secrets for decryption keys. We have to protect the encrypted bits, and since we’re just wasting our time with our 30 bit usable pass phrases, we should omit pass phrases and make life easier for authorized users.
I find it relatively easy to construct a memorable password/phrase that I believe to be secure. Contextual mnemonics and natural language that adheres to ordinary orthographic rules would make my bank password (if they didn’t limit one with eight to twelve alpha-numeric characters):
I’d never expected my bank to get robbed 1710 times!
…or something to that effect. The number can be generated from the context too, if you so desire. Look at the address of the bank or the phone number or the shape created when you enter said numbers on a keypad, or double and invert the number of teller windows…there are hundreds of possibilities. Each of us is a pattern-matching monster; leverage that latent ability to create patterns and associations from the noise around you
…So reading this, now I’m curious: disregarding that most places won’t actually let me use that password, have I missed anything important in terms of my actual methodology for creating it? Are there any glaring flaws that don’t boil down to “But people will never do it like that!”?
Cheers
I find it interesting that no one has mentioned Diceware. Diceware uses a list of 7,776 words, which are randomly chosen via dice rolls. The entropy of each word is log(7776)/log(2) = 12.9 bits.
Correspondingly, a 5-word Diceware passphrase would have an entropy of almost 65 bits. An 8-word passphrase will have an entropy of 103 bits.
Bias in word choice/selection is eliminated as the words chosen are picked via random dice rolls.
See: http://www.diceware.com/
Rune, #12: space is not that special. On average, it crops up every 4-5 characters – arguably a *reduction* in entropy.
Perhaps another angle to consider is the nature of the threat against which one is protecting. The test, above, shows remote network dictionary-attack; however, I suspect the multi-word strategy is more vulnerable to shoulder-surfing in person.
Personally I favour passwords where both hands are involved at less predictable intervals.
I’ve seen more and more this self-impose self-censorship.
Either you find the word acceptable or you don’t. Censorship is immoral and dishonest but this type of censorship is also plain stupid.
Whatever the meaning of those words it is carried by any substitute. So shit is unacceptable but excrement is and so is the coward’s way **** or !$%&€.
If people find those words “offensive” is because of their meaning and their meaning can be reproduce using the most harmless words.
But “offensiveness” is subjective and therefore not a measure of anything. They may find those words “offensive” but their right to not see or hear them does not superimpose on everyone else right to Free Speech. What they do is bullying is you should not follow the vocal hypocritical fanatics.
Consult for example the OED (Oxford English Dictionary) where you can see that the name Jesus has been corrupted into more than 100 different ways of what is called “profanity”.
People didn’t give their lives in past in defense of freedom so that we surrender it to a bunch of immoral and dishonest people.
Just say NO! to censorship. Say NO! to self-censorship!
1st commenter anon has the right idea.
Easy way to exponentially frustrate any attempt at breaking a passphrase:
Step 1. Learn a conlang (constructed language – Klingon, Na’vi, Elvish, Esperanto, etc.) or just use the dictionary of one and translate words 1:1 without regard to grammar
Step 2. Use said conlang as your passphrase language.
Personally, I’ve dabbled in Elvish and I’m of intermediate fluency in Na’vi. Klingon is somewhat on my radar. Maybe not for everyone, but definitely worth just opening a Dictionary.pdf and giving it a go if you’re concerned about having a >30bit password.
The more you put your own choice into your password, the weaker your password gets. Math doesn’t care about you. Math is math. It’s not personal; it’s not unpersonal. Math is just math. Nothing special.
Advanced cryptography certainly is not something you can teach yourself at home, so stop fooling yourself. Technology didn’t choose you. Use Diceware, get used to typing 24 characters, and really, move on to something else.
Maybe get better email than Patraeus, or audit your social media reports – like the ones at Spokeo, Social Intelligence, and the other eight to ten web companies that aggregate and sell scuttlebutt. There is a 90% chance that your boss is looking for you on one of those. Think of your next pay raise.
With Diceware, you can feel better just knowing that you have the best passwords on your block.